package com.nowcoder.Offer.Array;

import org.junit.Test;

/**
 * 统计一个数字在排序数组中出现的次数。
 */
public class GetTimeOfK {
    public int GetNumberOfK(int [] array , int k) {
        int l = findFirstK(array,k);
        int r = findLastK(array,k);

        if(l == -1 || r == -1) return 0;

        return r - l + 1;
    }

    public int findFirstK(int[] array, int k){
        int l=0, r=array.length-1;
        while(l<=r){
            int mid = (l + r) >>> 1;
            if(array[mid] > k){
                r = mid - 1;
            }else if(array[mid] < k){
                l = mid + 1;
            }else {
                if(mid == 0 || array[mid-1] != array[mid]) return mid;
                else r = mid - 1;
            }
        }
        return -1;
    }

    public int findLastK(int[] array, int k){
        int l=0, r=array.length-1;
        while(l<=r){
            int mid = (l + r) >>> 1;
            if(array[mid] > k){
                r = mid - 1;
            }else if(array[mid] < k){
                l = mid + 1;
            }else {
                if(mid == array.length-1 || array[mid+1] != array[mid]) return mid;
                else l = mid + 1;
            }
        }
        return -1;
    }

    @Test
    public void test(){
        int[] arr = { 1,2,2,3,4,4,5,5,6,7,8,9};
        System.out.println(GetNumberOfK(arr,4));
    }

}
